Computer speed may be increased using two general approaches: increase instruction execution speed or do more instruction execution in parallel. As instruction execution speed approaches the limits of electron mobility in silicon, parallelism becomes the best alternative to increasing computer speed.
Previous attempts at parallelism have included:
1. Overlapping next instruction fetching with current instruction execution.
2. Instruction pipelining. An instruction pipeline breaks each instruction into as many pieces as possible and then attempts to map sequential instructions into parallel execution units. Theoretical maximum improvement is seldom achieved due to the inefficiencies of multi-step instructions, inability of many software programs to provide enough sequential instructions to keep the parallel execution units filled, and the large time penalty paid when a branch, loop, or case construct is encountered requiring the refilling of the execution units.
3. Single instruction multiple data or SIMD. This type of technique is found in the Intel SSE instruction set, as implemented in the Intel Pentium 3 and other processors. In this technique, a single instruction executes on multiple data sets. This technique is useful only for special applications such as video graphics rendering.
4. Hypercube. This technique employs large two-dimensional arrays and sometimes three-dimensional arrays of processors and local memory. The communications and interconnects necessary to support these arrays of processors inherently limits them to very specialized applications.
A pipeline is an instruction execution unit consisting of multiple sequential stages that successively perform a piece of an instruction's execution, such as fetch, decode, execute, store, etc. Several pipelines may be placed in parallel, such that program instructions are fed to each pipeline one after another until all pipelines are executing an instruction. Then the instruction filling repeats with the original pipeline. When N pipelines are filled with instructions and executing, the performance effect is theoretically the same as an N times increase in execution speed for a single execution unit.
Successful pipelining depends upon the following:
1. An instruction's execution must be able to be defined as several successive states.
2. Each instruction must have the same number of states.
3. The number of states per instruction determines the maximum number of parallel execution units.
Since pipelining can achieve performance increases based on the number of parallel pipelines, and since the number of parallel pipelines is determined by the number of states in an instruction, pipelines encourage complex multi-state instructions.
Heavily pipelined computers very seldom achieve performance anywhere near the theoretical performance improvement expected from the parallel pipeline execution units. Several reasons for this pipeline penalty include:
1. Software programs are not made up of only sequential instructions. Various studies indicate changes of execution flow occur every 8-10 instructions. Any branch that changes program flow upsets the pipeline. Attempts to minimize the pipeline upset tend to be complex and incomplete in their mitigation.
2. Forcing all instructions to have the same number of states often leads to execution pipelines that satisfy the requirements of the lowest common denominator (i.e., the slowest and most complex) instructions. Because of the pipeline, all instructions are forced into the same number of states, regardless of whether they need them or not. For example, logic operations (such as AND or OR) execute an order of magnitude faster than an ADD, but often both are allocated the same amount of time for execution.
3. Pipelines encourage multi-state complex instructions. Instructions that might require two states are typically stretched to fill 20 states because that is the depth of the pipeline. (The Intel Pentium 4 uses a 20 state pipeline.)
4. The time required for each pipeline state must account for propagation delays through the logic circuitry and associated transistors, in addition to the design margins or tolerances for the particular state.
5. Arbitration for pipeline register and other resource access often reduces performance due to the propagation delays of the transistors in the arbitration logic.
6. There is an upper limit on the number of states into which an instruction may be split before the additional state actually slows down execution, rather than speeds it up. Some studies have suggested that the pipeline architecture in the last generation of Digital Equipment Corporation's Alpha processor exceeded that point and actually performed slower that the previous, shorter pipelined version of the processor.